package com.itheima.leetcode.od.b.greedy;

import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * (A卷,100分)- 最短木板长度（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 小明有 n 块木板，第 i ( 1 ≤ i ≤ n ) 块木板长度为 ai。
 * 小明买了一块长度为 m 的木料，这块木料可以切割成任意块，拼接到已有的木板上，用来加长木板。
 * 小明想让最短的模板尽量长。请问小明加长木板后，最短木板的长度可以为多少？
 * <p>
 * 输入描述
 * <p>
 * 输入的第一行包含两个正整数， n ( 1 ≤ n ≤ 10^3 ), m ( 1 ≤ m ≤ 10^6 )，n 表示木板数， m 表示木板长度。
 * 输入的第二行包含 n 个正整数， a1, a2,…an ( 1 ≤ ai ≤ 10^6 )。
 * <p>
 * 输出描述
 * <p>
 * 输出的唯一一行包含一个正整数，表示加长木板后，最短木板的长度最大可以为多少？
 * <p>
 * 用例
 * <p>
 * 输入	5 3
 * <p>
 * 4 5 3 5 5
 * <p>
 * 输出	5
 * <p>
 * 说明	给第1块木板长度增加1，给第3块木板长度增加2后，
 * 这5块木板长度变为[5,5,5,5,5]，最短的木板的长度最大为5。
 * <p>
 * 输入	5 2
 * <p>
 * 4 5 3 5 5
 * <p>
 * 输出	4
 * <p>
 * 说明	给第3块木板长度增加1后，这5块木板长度变为[4,5,4,5,5]，剩余木料的长度为1。此时剩余木料无论给哪块木板加长，最短木料的长度都为4。
 * <p>
 * 题目解析
 * <p>
 * 本题的题意是比较明确的，我的解题思路如下：
 * <p>
 * 要想让最短的木板尽可能长，那么我们就要不停地递进式补足最短板，比如用例输入有5个板：4 5 3 5 5，可用材料m=3
 * <p>
 * 最短的板长度是3，只有一个，那么我们就将他补足到4，此时消耗了一单位长度的材料，m=2
 * <p>
 * 这样的话，只剩下两种长度的板4，5，
 * <p>
 * 且4长度有两个，5长度有三个，最短板是长度4.
 * <p>
 * 接下来我们应该尽量将最短板4长度的板补足到5长度，而刚好剩余材料m=2，可以将所有4长度的板补足到5长度，此时所有板都是5长度，且材料耗尽。
 * <p>
 * 我们还需要考虑一种特殊情况，那就是m还有值，但是只剩下一种长度的板，此时我们应该平分材料到每一个板，
 * <p>
 * 假设只剩一种长度的板有count个，则平均分的话，每个板能分得 m / count 长度，这个值有可能是小数，我们举个例子：
 * <p>
 * 5个一样长度x的板，m = 13，则 13 / 5 = 2...3，因此最短板长度就是x+2，
 * <p>
 * 再比如
 * <p>
 * 5个一样长度x的板，m = 15，则 13 / 5 = 3，因此最短板长度就是x+3。
 * <p>
 * 本题有点贪心思维，即优先分配m的长度给最短板。
 * <p>
 * 关于算法的时间复杂度，由于板子数量最多1000个，因此统计相同长度板子数量的时间复杂度很低。
 * <p>
 * 然后m的长度达到了10^6，这就比较大了，但是我们通过不断递进式累计最短板数量，最终不会受到m长度的影响，只会受到板子数量的影响。
 * <p>
 * 因此下面整体复杂度是O(N)，且N取值最多是1000。
 */
public class ShortestPlankLength {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }*/

        String input1 = "5 3";
        String input2 = "4 5 3 5 5";

        int[] intArr = Arrays.stream(input1.split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        int n = intArr[0];
        int m = intArr[1];

        int[] a = Arrays.stream(input2.split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        System.out.println(getResult(m, a));
        System.out.println(getResult(n, m, a));
    }

    /**
     * 贪心
     *
     * @param m
     * @param a
     * @return
     */
    public static int getResult(int m, int[] a) {
        // 统计每种长度板的数量，记录到woods中，key是板长度，val是板数量
        HashMap<Integer, Integer> woods = new HashMap<>();
        Arrays.stream(a)
                .boxed()
                .forEach(ai -> woods.put(ai, woods.getOrDefault(ai, 0) + 1));

        // 将统计到的板，按板长度排优先级，长度越短优先级越高，这里使用优先队列来实现优先级
        PriorityQueue<Integer[]> pq = new PriorityQueue<>((b, c) -> b[0] - c[0]);
        for (Integer wood : woods.keySet()) {
            pq.offer(new Integer[]{wood, woods.get(wood)});
        }

        // 只要还有剩余的m长度，就将他补到最短板上
        while (m > 0) {
            // 如果只有一种板长度，那么就尝试将m平均分配到各个板上
            if (pq.size() == 1) {
                Integer[] info = pq.poll();
                int len = info[0];
                int count = info[1];
                return len + m / count;
            }

            // 如果有多种板长度
            // min1是最短板
            Integer[] min1 = pq.poll();
            // min2是第二最短板
            Integer[] min2 = pq.peek();

            // diff是最短板和第二最短板的差距
            int diff = min2[0] - min1[0];
            // 将所有最短板补足到第二短板的长度，所需要总长度total
            int total = diff * min1[1];

            // 如果m的长度不够补足所有最短板，那么说明此时最短板的长度就是题解
            if (total > m) {
                return min1[0] + m / min1[1];
            } else if (total == m) { // 如果m的长度刚好可以补足所有最短板，那么说明最短板可以全部升级到第二短板，且刚好用完m，因此第二短板的长度就是题解
                return min2[0];
            } else { // 如果m的长度足够长，能补足所有最短板到第二短板，还能有剩余，则将最短的数量加到第二短板的数量上，继续下轮循环
                m -= total;
                min2[1] += min1[1];
            }
        }

        return pq.peek()[0];
    }

    /**
     * <S>动态规划</S>
     * <p>
     * 贪心
     *
     * @param n   木板数量
     * @param m   可用的木料长度
     * @param arr 木板长度数组
     * @return 最短木板长度
     */
    public static int getResult(int n, int m, int[] arr) {
        // 木板长度升序
        Arrays.sort(arr);

        // dp用于保存将所有arr[i-1]长度的木板补足到arr[i]长度，所需要的木料长度
        int dp = 0;
        for (int i = 1; i < n; i++) {
            // 比如将arr[0]长度的木板补足到arr[1]所需的木料长度为arr[1] - arr[0]
            // 比如将arr[1]长度的木板补足到arr[2]所需的木料长度为(arr[2] - arr[1]) *
            // 2，注意这里*2的原因是arr[0]已经被补足到arr[1]长度了，因此arr[1]长度此时有2个
            int need = (arr[i] - arr[i - 1]) * i;

            // 如果m可用木料不满足上面，则将剩余可用m-dp的材料均分给i根木料，返回此时的最短木料
            if (dp + need > m) {
                return (m - dp) / i + arr[i - 1];
            }

            dp += need;
        }

        // 如果将所有木板都补足到最长木板的长度了，还有剩余木料可用，则均分
        return (m - dp) / n + arr[n - 1];
    }
}